package com.dkd.day20250727;

import java.util.*;

public class Main46 {
    //给一个无向图染色，可以填红黑两种颜色，必须保证相邻两个节点不能同时为红色，输出有多少种不同的染色方案？
    //
    //输入描述
    //第一行输入M(图中节点数) N(边数)
    //
    //后续N行格式为：V1 V2表示一个V1到V2的边。
    //
    //数据范围：1 <= M <= 15,0 <= N <= M * 3，不能保证所有节点都是连通的。
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int m = sc.nextInt();
        int n = sc.nextInt();

        int[][] arr = new int[n][2];
        for (int i = 0; i < n; i++) {
            arr[i][0] = sc.nextInt();
            arr[i][1] = sc.nextInt();
        }

    }

    public static void solve(int m, int n, int[][] arr) {
        HashMap<Integer, HashSet<Integer>> map = new HashMap<>();
        for (int[] edge : arr) {
            map.putIfAbsent(edge[0], new HashSet<>());
            map.get(edge[0]).add(edge[1]);

            map.putIfAbsent(edge[1], new HashSet<>());
            map.get(edge[1]).add(edge[0]);
        }

    }

    public static int dfs(HashMap<Integer, HashSet<Integer>> connect, int m, int index, int count,
                          LinkedList<HashSet<Integer>> path) {
        if(path.size() == m) return count;


        outer:
        for (int i = index; i <= m; i++) {
            // 如果新加入节点i和已有节点j相邻，则说明新加入节点不能染成红色，需要进行剪枝
            for (HashSet<Integer> p : path) {
                if (p.contains(i)) continue outer;
            }

            count++;

            if (connect.containsKey(i)) {
                path.addLast(connect.get(i));
                count = dfs(connect, m, i + 1, count, path);
                path.removeLast();
            } else {
                count = dfs(connect, m, i + 1, count, path);
            }
        }

        return count;
    }
}
